#include "linearList.h"
#include <iostream>
using namespace std;

sequenceList::sequenceList(const int& listsize, const int& high, float list[])
{
	maxCapcity=listsize;
	curNumberOfItem=high;
	myList=new float[listsize];
	for(int i=0;i<curNumberOfItem;i++){
		myList[i]=list[i];
	}
	
} 

sequenceList::~ sequenceList ()
{
	delete[] myList;
}

bool sequenceList::addItem(const float&data){
	if(curNumberOfItem>=maxCapcity){
		return false;
	}
	else{
		myList[curNumberOfItem]=data;
		curNumberOfItem++;
		return true;
	}
}

bool sequenceList::insertItem(const int& index, const float& data){
	if(index<0||index>curNumberOfItem||curNumberOfItem>=maxCapcity){
		return false;
	}
	else{
		for(int i=curNumberOfItem-1;i>=index;i--){
			myList[i+1]=myList[i];
		}
		myList[index]=data;
		curNumberOfItem++;
		return true;
	}
}

int sequenceList::deleteItem(const float& data){
	for(int i=0;i<curNumberOfItem-1;i++){
		if(myList[i]==data){
			for(int j=i;j<=curNumberOfItem-1;j++){
				myList[j]=myList[j+1];
			}	
			curNumberOfItem--;
			return i;
		}
	}
	return -1;
}
bool sequenceList::locate(const int&number, float& val){
	if(number<1||number>curNumberOfItem){
		return false;
	}
	else{
		val=myList[number-1];
		return true;
	}
	
}

int sequenceList::locate(const float&data){
	for(int i=0;i<curNumberOfItem;i++){
		if(myList[i]==data){
			return i;
		}
	}
	return -1;
}

void sequenceList::reverse(){
	for(int i=0;i<curNumberOfItem/2;i++){
		float data=myList[i];
		myList[i]=myList[curNumberOfItem-1-i];
		myList[curNumberOfItem-1-i]=data;
	}
}


//顺序表打印
void sequenceList::print()
{
    cout << curNumberOfItem << ":";

    for(int i = 0; i < curNumberOfItem-1; i++)
    {
        cout << myList[i] << ",";
    }

    cout << myList[curNumberOfItem-1] << endl;
}

listNode::~listNode(){
}

linkList::linkList(){
	firstNode=new listNode;
	curNode=new listNode;
	lastNode=new listNode;
	firstNode->next=NULL;
	curNode->next=NULL;
	lastNode->next=NULL;
	listSize=0;
}

linkList::linkList(const int& size, float link[]){
	listSize=size;
	firstNode=new listNode;
	listNode* now = firstNode;
	for (int i = 0; i < listSize; i++)
    {
        now->next = new listNode;
        now->next->data = link[i];
        now = now->next;
    }
    lastNode=now;
}

linkList::~linkList(){
	listNode* a=firstNode;
	for (int i = 0; i < listSize; i++){
		listNode* b;
		b=a->next;
		delete a;
		a=b;
	}
}

bool linkList::headInsertItem(const float& num){
	listNode* temp=new listNode;
	if(temp==NULL){
		return false;
	}
	else{
		temp->data=num;
		temp->next=firstNode->next;
		firstNode->next=temp;
		listSize++;
		return true;
	}
}

bool linkList::tailInsertItem(const float&num){
	listNode* temp=new listNode;
		if(temp==NULL){
			return false;
		}
		listNode* now=firstNode;
		while(now->next!=NULL){
			now=now->next;
		}
		temp->data=num;
		now->next=temp;
		lastNode=temp;
		listSize++;
		return true;
	
}

int linkList::insertItem(const int& index, const float&num){
	listNode* temp=new listNode;
	if(index<0||index>listSize){
		return -1;
	}
	else{
		listNode* now=firstNode;
		int i=0;
		while(i<index){
			now=now->next;
			i++;
		}
		temp->data=num;
		temp->next=now->next;
		now->next=temp;
		listSize++;
		return index;
	}
}

int linkList::deleteItem(const float& num){
	listNode* now=firstNode;
	listNode* temp=new listNode;
	for(int i=0;i<listSize;i++){
		now=now->next;
		if(now->next->data==num){
			temp=now->next;
			now->next=temp->next;
			delete temp;
			listSize--; 
			return i+1;
			
		}
	}
	return -1;
}

bool linkList::locate(const int& index, float& val){
	listNode* now=firstNode;
	if(index<0||index>=listSize){
		return false;
	}
	for(int i=0;i<=index;i++){
		now=now->next;	
	}
	val=now->data;
	return true;
}

int linkList::locate(const float&num){
	listNode* now=firstNode;
	for(int i=0;i<listSize;i++){
		now=now->next;	
		if(now->data==num){
			return i;
		}
	}
	 return -1;
}

void linkList::ascendingOrder(){
	if(listSize<=1){
		return;
	}
	float a;
	listNode* temp=new listNode;
	for(int i=0;i<listSize;i++){
		listNode* now=firstNode->next; 
		for(int j=0;j<listSize-1-i;j++){
			temp=now;
			now=now->next;
			if(temp->data>now->data){
				a=temp->data;
				temp->data=now->data;
				now->data=a;
			}
		}
	}
}

listNode* linkList::getPtr(int index)
{
    if (index >= listSize)
        return NULL;
    listNode* now = firstNode;
    for (int i = 0; i <= index; i++)
        now = now->next;
    return now;
}

void linkList::reverse()
{
    for (int i = 0; i < listSize / 2; i++)
    {
        listNode* p1 = getPtr(i);
        listNode* p2 = getPtr(listSize - i - 1);
        float temp = p1->data;
        p1->data = p2->data;
        p2->data = temp;
    }
}


//链表打印

void linkList::print()
{
    curNode = firstNode;

    cout << listSize << ":";

    while(curNode != lastNode)
    {
        if(curNode->next == lastNode)
            cout << curNode->next->data << endl;
        else
        {
            cout << curNode->next->data << ",";
        }
        
        
        curNode = curNode->next;
    }
}

void merge(linkList& A, linkList& B){
	A.reverse();
	B.reverse();
	listNode* a=new listNode; 
	listNode* b=new listNode;
	float a1;
	float b1;
	int i=0;
	a=A.firstNode;
	b=B.firstNode;
	while(a->next!=NULL&&b->next!=NULL){
		a1=a->next->data;
		b1=b->next->data;
		if(a1>=b1){
		a=a->next;
		i++;
		}
		else{
			A.insertItem(i,b1);
			a=a->next;
			b=b->next;
			i++;
		}
	}
	while(a->next!=NULL){
		a=a->next;
	}
	while(b->next!=NULL){
		b1=b->next->data;
		A.tailInsertItem(b1);
		b=b->next;
		A.lastNode=b;
		}
	return;	
}
